package 算法_递归分治;

import java.util.Arrays;

public class Merge_Sort {
    public static void main(String[] args) {
        int[] a = {2, 5, 6, 2, 1, 4, 6, 8, 90};
        merge_sort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void merge_sort(int[] a, int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            merge_sort(a, l, m);
            merge_sort(a, m + 1, r);
            merge(a, l, m, r);
        }
    }

    private static void merge(int[] a, int l, int m, int r) {
        int[] b = new int[r - l + 1];
        int i = l, j = m + 1, idx = 0;
        while (i <= m && j <= r)
            b[idx++] = (a[j] >= a[i]) ? a[i++] : a[j++];
        while (i <= m)
            b[idx++] = a[i++];
        while (j <= r)
            b[idx++] = a[j++];
        System.arraycopy(b, 0, a, l, b.length);
    }
}
